#include <stdio.h>

/*
 * 除法优化之有符号非2的幂优化
 */

int main(int argc, char* argv[]) 
{ 
	int NumberOne = 0; 
	int NumberTwo = 0;

	scanf("%d", &NumberOne);
	scanf("%d", &NumberTwo);

	int Count1 = NumberOne / 3;

	int Count2 = NumberTwo / 5;

	int Count3 = NumberTwo / 6;

	int Count4 = NumberTwo / 9;

	printf("%d %d %d %d",Count4, Count3, Count2, Count1);

	return 0;
}

#if 0
	.text:00401000 ; int __cdecl main(int argc, const char **argv, const char **envp)
	.text:00401000 _main proc near ; 
	CODE XREF: start+AF↓p
	.text:00401000
	.text:00401000 var_8 = dword ptr -8
	.text:00401000 var_4 = dword ptr -4
	.text:00401000 argc = dword ptr 4
	.text:00401000 argv = dword ptr 8
	.text:00401000 envp = dword ptr 0Ch
	.text:00401000.text:00401000 sub esp, 8
	.text:00401003 xor eax, eax
	.text:00401005 mov [esp+8+var_8], eax
	.text:00401009 mov [esp+8+var_4], eax
	.text:0040100D lea eax, [esp+8+var_8]
	.text:00401011 push eax
	.text:00401012 push offset aD ; "%d"
	.text:00401017 call _scanf
	.text:0040101C lea ecx, [esp+10h+var_4]
	.text:00401020 push ecx
	.text:00401021 push offset aD ; "%d"
	.text:00401026 call _scanf

	//第一段
	.text:0040102B mov ecx, [esp+18h+var_8]
	.text:0040102F mov eax, 55555556h
	.text:00401034 imul ecx
	.text:0040103A mov eax, edx             // 2^32+0 / 0x55555556 = 3
	.text:0040103C shr eax, 1Fh
	.text:0040103F add edx, eax

	//第二段
	.text:00401036 mov ecx, [esp+18h+var_4]
	.text:00401041 mov eax, 66666667h
	.text:00401047 imul ecx
	.text:00401049 sar edx, 1           // 2^(32+1) / 0x66666667 (1717986919) = 4.9999999 = 5
	.text:0040104B mov eax, edx
	.text:0040104D shr eax, 1Fh
	.text:00401050 add edx, eax
	.text:00401057 push edx //这里原先是流水线优化给提到上边来了

	//第三段
	.text:00401052 mov eax, 2AAAAAABh
	.text:00401058 imul ecx
	.text:0040105A mov eax, edx     // 2^(32+0) / 0x2AAAAAAB (715827883) = 5.99999999 = 6
	.text:0040105C shr eax, 1Fh
	.text:0040105F add edx, eax
	.text:00401066 push edx //同上流水线优化

	//第四段
	.text:00401061 mov eax, 38E38E39h
	.text:00401067 imul ecx
	.text:00401069 sar edx, 1
	.text:0040106B mov ecx, edx     // 2^(32+1) / 0x38E38E39 (954437177) = 8.9999999 = 9
	.text:0040106D shr ecx, 1Fh
	.text:00401070 add edx, ecx
	.text:00401072 push edx
	.text:00401073 push offset aDDDDD ; "%d%d%d%d%d"
	.text:00401078 call _printf
	.text:0040107D push offset aPause ; "pause"
	.text:00401082 call _system
	.text:00401087 xor eax, eax
	.text:00401089 add esp, 30h
	.text:0040108C retn
	.text:0040108C _main endp

/*
 * 除法非2的幂还原
 */
	在除法算式中,被除数在"÷"的前面,除数 在"÷"的后面; 
	在分数中,被除数占据分子的位置,除数占据分母的位置。

	如果想要直接还原，那么我们把代码定式提取出来，直接进行还原。

	mov ecx, 被除数 
	mov eax, M值
	imul ecx 
	sar edx, n
	mov eax, edx
	shr eax, 1Fh
	add edx, eax
	push edx

	根据汇编我们只需要看三个点即可，并且得出三个点的公式得原理：

		(ecx * M) 
		---------
		(2^n + 1)

	其中M是编译器计算出来了， ecx是被除数，这里sar n值，直接操作的是edx。
	
	这里其实是除法转变为了乘法，而如果 除法转变为乘法，那么在32位年代下，两个数相乘32的值是不会放下的。
	所以我们这里其实使用的是 edx,eax 来代表乘法的结果，然后直接操作了 乘积的高位，这里右移1，等价于是除以2^n+1。

	那么还原的时候直接记住死公式就可以，2^32+1 / M 。

	直接统计 n 的取值，然后用 2的32次方 + n 即可。
	
	因为乘积的低位时代表2^32次方，这里直接是对乘积高位做操作，所以我们需要加上低位的32次方的值。


	以上例子还原如下:

		.text:0040102B mov ecx, [esp+18h+var_8]
		.text:0040102F mov eax, 55555556h		// 1431655766
		.text:00401034 imul ecx
		.text:0040103A mov eax, edx //这里直接使用的是edx.而没有对edx做修改.所以我们的n值就是0
		.text:0040103C shr eax, 1Fh
		.text:0040103F add edx, eax

	套用公式：
		2^32+0 / 0x55555556 = 2.99999999979
		2.99直接向上取整 = 3，所以这里我们就寻得被除数为3。


/*
 * 除数为非2的幂的优化与原理
 */
	.text:00401061 mov eax, 38E38E39h	# 954437177
	.text:00401067 imul ecx
	.text:00401069 sar edx, 1
	.text:0040106B mov ecx, edx

	.text:0040106D shr ecx, 1Fh
	.text:00401070 add edx, ecx
	.text:00401072 push edx

	这里我们汇编分为两部分。上边是可以直接套用公式还原，而下方其实是获取符号位，调整一下符号位。

	shr 逻辑右移最高位以0填充，右移31(1F)位 取得符号位，然后这里有一个加法。
	其实这个加法也是套路，跟之前讲解的无分支优化差不多。

	如果结果是正数那么 add edx,eax 就是加0，等于什么都不干；
	如果是结果是负数那么我们就需要除法的商做调整，做加1调整。

    2^(32+1) / 954437177 = 8.99999999999 = 9

/*
 * 除法转化为乘法的原理
 */

	如果想要了解为什么非2的幂代码会变成上面的代码，就要理解下原理。

	设 a = 被除数 , b = 除数(是一个常量值) ===>  a ÷ b , 那么就会有以下公式：

                            1*2n           2n     1
	a/b <=> a * 1/b <=> a * ----- <=> a * ---- * ---
                            b*2n           b      2n
						
	这个就是上面所了解的分数相关知识。

	看最后的公式：

         2n     1
    a * ---- * ---
         b      2n

	其中 2n/b这个是可以在编译期中计算出来的，VC++6.0 或者VS2019 在编译期间 n 的取值是大于32的，所以是可以算出来的。

	所以公式可以变为如下，在这里把编译器可以计算出来的值记做 C 。那么可以得出以下公式：

        2n
    a * ---
         b             a * c
    ---------	==>   ----  ==> (a * c) >> n
		2n              2n

	最终简化为就是 (a * c) >> n，而反过头来看我们的汇编代码：

	.text:00401061 mov eax, 38E38E39h	# 954437177
	.text:00401067 imul ecx
	.text:00401069 sar edx, 1

	列出公式：

	ecx = 被除数

	eax = M 等价于 2n/b 的值.

	ecx eax / 2^33 这条公式就正好对应着 除法转变为乘法的原理，和上面的公式一样，(a c) >> n。

	所以我们解方程即可， 2^n / b = M值，那么 2^n / M = b ，b 就是我们的要求的除数，所以得出我们的除数。 

/*
 * 除法的还原公式
 */
          2n
    2n /  --   ==>  2n / c
           b
	这里的 C 其实就是 2^n / b，在汇编中我们也设为M，所以也可以写为如下：

	除法转变为乘法的公式：

                            1*2n           2n     1
	a/b <=> a * 1/b <=> a * ----- <=> a * ---- * ---
                            b*2n           b      2n

	转变为如下：

         2n     1
    a * ---- * ---
         b      2n

	继续转变：

        2n
    a * ---
         b             a * c
    ---------	==>   ----  ==> (a * c) >> n
		2n              2n

	最终转变：

	对于上面记住代码定式也可以进行还原，当然熟悉除法转变为乘法的原理更好。

	高级代码看其特征我们发现其实是一样的，都可以使用除法转乘法的公式来进行还原。

	除法还原公式其实就是解方程了，解开就可以得到被除数。





https://www.sohu.com/a/421762589_120054144
gcc反编译后如何确定除数
#endif
